// https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

// 算法思路总结：
// 1. 归并排序过程中统计右侧较小元素数量
// 2. 使用索引数组跟踪元素原始位置
// 3. 合并时当左元素大于右元素时更新计数
// 4. 计数为当前右半部分剩余元素个数
// 5. 时间复杂度：O(n log n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> countSmaller(vector<int>& nums) 
    {
        int m = nums.size();
        vector<int> counts(m);

        vector<int> index(m);
        for (int i = 0 ; i < m ; i++)
        {
            index[i] = i;
        }

        mergesort(nums, index, 0, m - 1, counts);

        return counts;
    }

    void mergesort(vector<int>& nums, vector<int>& index, int left, int right, vector<int>& counts)
    {
        if (left >= right)
        {
            return ;
        }

        int mid = (left + right) >> 1;
        mergesort(nums, index, left, mid, counts);
        mergesort(nums, index, mid + 1, right, counts);

        int cur1 = left, cur2 = mid + 1, tmpindex = 0;
        vector<int> tmp(right - left + 1);

        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[index[cur1]] <= nums[index[cur2]])
            {
                tmp[tmpindex++] = index[cur2++];
            }
            else
            {
                counts[index[cur1]] += right - cur2 + 1;
                tmp[tmpindex++] = index[cur1++];
            }
        }

        while (cur1 <= mid)
        {
            tmp[tmpindex++] = index[cur1++];
        }

        while (cur2 <= right)
        {
            tmp[tmpindex++] = index[cur2++];
        }

        for (int i = left ; i <= right ; i++)
        {
            index[i] = tmp[i - left];
        }
    }
};

int main()
{
    vector<int> nums1 = {5,2,6,1}, nums2 = {-1,-1};
    Solution sol;

    auto count1 = sol.countSmaller(nums1);
    auto count2 = sol.countSmaller(nums2);

    for (const int& num : count1)
    {
        cout << num << " ";
    }
    cout << endl;

    for (const int& num : count2)
    {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}